#include "Huffman.h"
#define maxWeight 32767

void createHFTree(HFTree& HT, char value[], int fr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		HT.elem[i].data = value[i];
		HT.elem[i].weight = fr[i];
	}
	for (int i = 0; i < leafNumber; i++)
	{
		HT.elem[i].parent = HT.elem[i].lchild = HT.elem[i].rchild = -1;
	}
	int min1, min2;
	int s1, s2;
	for (int i = n; i < 2 * n - 1; i++)
	{
		min1 = min2 = maxWeight;
		s1 = s2 = 0;
		for (int k = 0; k < i; k++)
		{
			if (HT.elem[k].parent == -1)
			{
				if (HT.elem[k].weight < min1)
				{
					min2 = min1;
					s2 = s1;
					min1 = HT.elem[k].weight;
					s1 = k;
				}
				else if (HT.elem[k].weight < min2)
				{
					min2 = HT.elem[k].weight;
					s2 = k;
				}
			}
		}
		HT.elem[s1].parent = HT.elem[s2].parent = i;
		HT.elem[i].lchild = s1;
		HT.elem[i].rchild = s2;
		HT.elem[i].weight = HT.elem[s1].weight + HT.elem[s2].weight;
	}
	HT.num = n;
	HT.root = 2 * n - 2;
}